package sort.leetcode_57_hard_sort;

import java.util.ArrayList;
import java.util.List;

public class InsertMerge {
    /**
     * 插入区间：如果插入的区间和原区间有重叠，就合并。
     *
     * @param intervals   给定原区间集合
     * @param newInterval 给定新的区间，插入到原区间中
     * @return 返回插入后的结果。
     * <p>
     * 1. 最直接的方法就是将新区间直接插入，然后按开始端点排个序，之后进行56题的操作即可。
     * <p>
     * 但是该题中的原区间已经是有序的。
     * <p>
     * 2. 从原区间开始 向右寻找
     * 情况分析：
     * 1. 插入区间跟原集合中的区间都没有重叠，按顺序依次加入List即可
     * 2. 插入区间跟原集合中的区间有重叠部分
     *      1. 先将无重叠部分加入List
     *      2. 无重叠过滤后，来到有重叠部分，寻找重叠条件：结束端点 > 开始端点， 合并后加入List
     *      3. 将后面不重叠部分依次加入List（如果有）
     *
     * intervals：{1,2}, {3,5}, {6,7}, {8,10}, {12,14};
     * newIntervals：{4,8};
     *
     * 左边不重叠部分：{1,2}，原区间结束 < 插入区间开始
     * 中间重叠部分：{3,5}, {6,7}, {8,10}，合并：{3,10};   原区间开始 < 插入区间结束
     *      注意，为什么不能是 原区间结束 > 插入区间开始, (这个条件看上去也是符合重叠部分的条件)
     *          如果使用此条件，14还是 > 插入区间的开始4，那么最终还会跟{12,14}这个区间在进行一次合并
     *
     * 右边不重叠：{12,14}; 原区间开始 > 插入区间结束
     */
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0) {
            return new int[][]{newInterval};
        }
        List<int[]> res = new ArrayList<>();
        //先把前面不重叠的部分（如果有）加入List：不重叠的条件就是原区间的结束 < 插入区间的开始
        int left = 0;
        while (left < intervals.length && intervals[left][1] < newInterval[0]) {
            res.add(intervals[left]);
            left++;
        }
        /**
         *
         * 此时前面不重叠的部分已经过滤掉，那么此时要么区间已经插入完毕，都是没有重叠的，要么就是到了有重叠的部分。
         * 开始合并重叠的部分：结束 > 开始 就是有重叠
         */
        while (left < intervals.length && intervals[left][0] <= newInterval[1]) {
            //选择合并后的开始端点和结束端点
            newInterval[0] = Math.min(intervals[left][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[left][1], newInterval[1]);
            left++;
        }
        res.add(newInterval);
        while (left < intervals.length) {
            res.add(intervals[left++]);
        }
        return res.toArray(new int[res.size()][]);
    }
}
